//https://www.yuque.com/huantaipingyang-jucwl/ipzeev/eefscuipsf3kp2og#q6K8K
//作用：单调递增栈：一个数组，计算每一个数，左边第一个比自己小的数在哪，右边第一个比自己小的数在哪。
//作用：单调递减栈：一个数组，计算每一个数，左边第一个比自己大的数在哪，右边第一个比自己大的数在哪。

#include <vector>
#include <stack>
#include <list>
#include <map>

using namespace std;

class Solution{
public:
    static std::vector<std::pair<int,int>> getNearLess(std::vector<int> arr) {
        std::vector<std::pair<int,int>> res(arr.size(),{-1,-1});
        std::stack<std::list<int>> stack;
        for(size_t i=0;i<arr.size();++i){
            while(!stack.empty()&& arr[stack.top().back()] > arr[i]) {
                std::list<int> popIs=stack.top();
                stack.pop();
                int leftlessIndex = stack.empty()? -1:stack.top().back();
                for(int popi:popIs){
                    res[popi].first = leftlessIndex;
                    res[popi].second = i;
                }
            }
            if(!stack.empty() && arr[stack.top().back()] == arr[i]) {
                stack.top().push_back(i);
            }else{
                std::list<int> list = {(int)i};
                stack.push(list);
            }
        }
        while(!stack.empty()){
            list<int> popIs=stack.top();
            stack.pop();
            int leftlessIndex = stack.empty()? -1:stack.top().back();
            for(int popi:popIs) {
                res[popi].first = leftlessIndex;
                res[popi].second = -1;
            }
        }
        return res;
    }
};